设计哈希映射(Leetcode 706)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 2k | 阅读时长 ≈ 8
Leetcode 706

1

题目分析

   这个题目非常有价值，小伙伴们包括我也常常会出现一些问题，就是非常清楚哈希表的使用方法，但是让自己定义哈希表时就两眼抹黑，不知道如何下手。这也是年轻人普遍存在的问题，就像被制裁一样，为什么被制裁？就是因为我们拿到了一些上层的技术，直接使用非常方便，不去研究底层的原理，一旦不提供给我们上层技术，那么我们建造的大楼就会摇摇欲坠。这里也不过多深入讨论这个社会现象，因此小伙伴们在享受胜利果实的时候，一定要清楚底层的原理，这样才能在这个行业走得更远。

投机取巧法

这个题目定义为简单题，可能是使用投机取巧法，因为所有值都是在[0, 1000000]以内，而且全都是整型，因此我们直接建立一个长度为1000001的数组，键就是索引，值就是索引对应的值即可。

这个方法只能解决这个问题，如果键的范围特别大则无法使用这种方法。因此这个方法不是一个通用解法。

算法每次操作的**时间复杂度为$O(1)$，空间复杂度为$O(m)$**，m为数据范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MyHashMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = [-1] * 1000000

    def put(self, key, value):
        """
        value will always be non-negative.
        :type key: int
        :type value: int
        :rtype: None
        """
        self.dic[key] = value

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        return self.dic[key]

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: None
        """
        self.dic[key] = -1

开放寻址法

一个较好的方法是开放寻址法，就像办理业务一样，每一个键都对应一个服务台，如果有两个键对应同一个服务台，即发生了冲突，则顺次寻找下一个服务台。

初始时都默认为一个不会被取到的值，在这里就默认为-1，说明没有人占用该服务台。

插入键值对时：如果某个哈希值为k，则k服务台被占用，当下一次某个哈希值为k时，依次向下寻找，如果该键不是-1，说明被占用，比较两个键是否相等，如果相等则替换值即可，如果不相等继续向下寻找。找到第一个空位置-1时，将该位置放入键值对即可。

获取值时：当键对应的哈希值为k时，依次向下寻找，如果该键不是-1，说明被占用，比较两个键是否相等，如果相等则返回值即可，如果不相等继续向下寻找。找到第一个空位置-1时，说明没有找到该元素，返回-1。

删除键值对时：这个要特别注意，当键对应的哈希值为k时，依次向下寻找，如果该键不是-1，说明被占用，比较两个键是否相等，如果相等则将键值对改为-2，不能改成-1，小伙伴们想一想为什么？如果不相等继续向下寻找，找到第一个空位置-1时，说明没有找到该元素，不用删除操作，直接return即可。

如果改成-1，那么后面的就会被切断了，举个例子，(2, 2)，(5, 5)，(8, 8)中的键都对应哈希值10，那么插入时，dic[10] = (2, 2)，dic[11] = (5, 5), dic[12] = (8, 8)，如果删除了(5, 5)，则先检查dic[10]，发现键不相等，则继续寻找dic[11]，发现匹配，则将dic[11]改成[-1, -1]，那么下一次查找(8, 8)时，也是先检查dic[10]，发现不相等，继续寻找dic[11]，发现-1，则不继续寻找了。这就会产生问题。因此要改成-2。

因此这种方法的局限性也很容易的看出，就是会浪费大量内存，需要内存数量大于操作次数。

算法最坏情况下时间复杂度为$O(n)$，均摊每次操作的时间复杂度为$O(1)$，空间复杂度为$O(n)$**，其中n为操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def my_hash(key):
    return key % 10007


class MyHashMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = [[-1, -1] for _ in range(10007)]

    def put(self, key, value):
        """
        value will always be non-negative.
        :type key: int
        :type value: int
        :rtype: None
        """
        hash_key = my_hash(key)
        while self.dic[hash_key][0] != -1:
            if self.dic[hash_key][0] == key:
                self.dic[hash_key][1] = value
                return 
            hash_key = (hash_key + 1) % len(self.dic)
        self.dic[hash_key] = [key, value]

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        hash_key = my_hash(key)
        while self.dic[hash_key][0] != -1:
            if self.dic[hash_key][0] == key:
                return self.dic[hash_key][1]
            hash_key = (hash_key + 1) % len(self.dic)
        return -1

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: None
        """
        hash_key = my_hash(key)
        while self.dic[hash_key][0] != -1:
            if self.dic[hash_key][0] == key:
                self.dic[hash_key] = [-2, -2] 
            hash_key = (hash_key + 1) % len(self.dic)

拉链法

拉链法是我认为最优的解法，不会浪费大量内存，但是需要用链表保存，需要额外的空间存放指针，而且代码写起来较为繁琐。

其解决冲突的思想是，将每一个哈希值对应一个链表，节点的值为一个二元组，第一个元素为键，第二个元素为值。

插入键值对时：如果某个哈希值为k，寻找第k个链表，从头到尾进行遍历，如果链表某个节点的第一个元素等于键，则直接将第二个元素修改为值即可，如果遍历到链表尾部，则在尾部插入一个节点，该节点的值为键值对即可。

获取值时：如果某个哈希值为k，寻找第k个链表，从头到尾进行遍历，如果链表某个节点的第一个元素等于键，则直接将第二个元素返回即可，如果遍历到链表尾部，则返回-1。

删除键值对时：如果某个哈希值为k，寻找第k个链表，从头到尾进行遍历，如果链表某个节点的第一个元素等于键，则直接将该节点的上一个节点指向该节点的下一个节点即可，如果遍历到链表尾部，则没有找到该键值对，不需要进行任何操作。

算法最坏情况下时间复杂度为$O(n)$，均摊每次操作的时间复杂度为$O(1)$，空间复杂度为$O(n)$**，其中n为操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Linklist:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next


def my_hash(key):
    return key % 10007


class MyHashMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = [Linklist([None, None]) for _ in range(10007)]

    def put(self, key, value):
        """
        value will always be non-negative.
        :type key: int
        :type value: int
        :rtype: None
        """
        hash_key = my_hash(key)
        p = self.dic[hash_key]
        while p.next:
            if p.next.val[0] == key:
                p.next.val[1] = value
                return
            else:
                p = p.next
        p.next = Linklist([key, value])

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        hash_key = my_hash(key)
        p = self.dic[hash_key]
        while p:
            if p.val[0] == key:
                return p.val[1]
            else:
                p = p.next
        return -1

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: None
        """
        hash_key = my_hash(key)
        p = self.dic[hash_key]
        pre, cur = p, p.next
        while cur:
            if cur.val[0] == key:
                pre.next = cur.next
                return
            else:
                pre, cur = cur, cur.next

刷题总结

  这个题目真是太妙了，考察了常用数据结构的创建，也许今后小伙伴们可以直接使用dict数据结构，不需要手动创建，但是摆脱拿过来直接用的思维惰性是非常非常重要的。

-------------本文结束感谢您的阅读-------------
0%